package cn.jietuo.first.class07;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @author zhangx & jietuo_zx@163.com
 * @version 1.0
 * @date 2020/7/20
 * @description: 二叉树的序列化与反序列化
 */
public class Code04_SerializationAndDeserialization {

    public static class Node {
        public int value;
        public Node left;
        public Node right;

        public Node(int value) {
            this.value = value;
        }
    }

    /**
     * 序列化一个二叉树
     * 先序遍历
     *
     * @param head
     * @return
     */
    public static Queue<Integer> preSerializationBT(Node head) {
        Queue<Integer> ans = new LinkedList<>();
        pres(head, ans);
        return ans;
    }

    private static void pres(Node head, Queue<Integer> ans) {
        if (head == null) {
            ans.add(null);
        } else {
            pres(head.left, ans);
            pres(head.right, ans);
        }
    }

    /**
     * 反序列化二叉树
     *
     * @param data
     * @return
     */
    public static Node dePreSerializationBT(Queue<Integer> data) {
        if (data == null || data.size() < 1) {
            return null;
        }
        return dePres(data);
    }

    private static Node dePres(Queue<Integer> data) {
        Integer poll = data.poll();
        if (poll == null) {
            return null;
        }
        Node head = new Node(poll);
        head.left = dePres(data);
        head.right = dePres(data);
        return head;
    }

    /**
     * 后续遍历序列化二叉树
     *
     * @param head
     * @return
     */
    public static Queue<Integer> lastSerializationBT(Node head) {
        if (head == null) {
            return null;
        }
        Queue<Integer> queue = new LinkedList<>();
        lastSer(head, queue);
        return queue;
    }

    private static void lastSer(Node head, Queue<Integer> queue) {
        if (head == null) {
            queue.add(null);
        } else {
            lastSer(head.left, queue);
            lastSer(head.right, queue);
            queue.add(head.value);
        }
    }

    /**
     * 后续遍历反序列化
     *
     * @param queue
     * @return
     */
    public static Node deLastSerializationBT(Queue<Integer> queue) {
        if (queue == null || queue.size() < 1) {
            return null;
        }
        return deSer(queue);
    }

    private static Node deSer(Queue<Integer> queue) {
        Integer poll = queue.poll();
        if (poll == null) {
            return null;
        }
        Node node = new Node(poll);
        node.left = dePres(queue);
        node.right = dePres(queue);
        return null;
    }

}
